#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head)
{
	struct Node* cur = head;
	struct Node* next = cur->next;

	//赋值链接
	while (cur)
	{
		struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
		copy->val = cur->val;

		copy->next = cur->next;
		cur->next = copy;

		cur = next;
		next = cur->next;

	}
	//恢复cur和copy的初始位置
	cur = head;
	struct Node* copy = cur->next;
	next = copy->next;
	//置random
	while (cur)
	{
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}

		cur = next;
		copy = next->next;
		next = cur->next;
	}
	//新的链表的头结点和尾节点
	struct Node* tail = NULL;
	struct Node* newhead = NULL;
	//恢复cur和copy的位置
	cur = head;
	copy = cur->next;
	next = copy->next;
	while (cur)
	{
		if (tail == NULL)
		{
			tail = newhead = copy;
		}
		else
		{
			tail->next = copy;
			tail = tail->next;
		}
		cur = copy->next;
		copy = next->next;
	}

	return newhead;
}